package io.github.handyang.algorithms.digraph;

import com.google.common.collect.Lists;

import java.util.List;

/**
 * 寻找有向环
 */
public class DirectedCycle {
    private final Digraph digraph;
    private final boolean[] marked;
    private final List<Integer> cycle = Lists.newArrayList();

    public DirectedCycle(Digraph digraph) {
        this.digraph = digraph;

        this.marked = new boolean[digraph.V()];
        if (dfs(0)) {
            cycle.add(0);
        }
    }

    private boolean dfs(int start) {
        marked[start] = true;

        for (Integer point : digraph.adj(start)) {
            if (marked[point]) return true;

            if (dfs(point)) {
                cycle.add(point);
                return true;
            }

            marked[point] = false;
        }

        return false;
    }

    boolean hasCycle() {
        return !this.cycle.isEmpty();
    }

    Iterable<Integer> cycle() {
        return this.cycle;
    }

}
